package leetcode.simple._100;

import structure.tree.TreeNode;

import java.util.Stack;

/**
 * @author mgl
 * @version 1.0
 * @description 第100道题，判断两棵二叉树是否为同一棵树
 * @date 2023/7/8 22:47
 */
public class SameTree {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public boolean isSameTree_old(TreeNode p, TreeNode q) {
        if ((p == null && q != null) || (q == null && p != null)) return false;

        Stack<TreeNode> stack_p = new Stack<>();
        Stack<TreeNode> stack_q = new Stack<>();

        stack_p.push(p);
        stack_q.push(q);

        while ((!stack_q.isEmpty()) && (!stack_q.isEmpty())) {
            TreeNode treeNode_p = stack_p.pop();
            TreeNode treeNode_q = stack_q.pop();

            if (treeNode_p.val != treeNode_q.val) return false;

            if ((treeNode_p == null && treeNode_q != null) || (treeNode_q == null && treeNode_p != null)) return false;
            if (treeNode_p.left != null) stack_p.push(treeNode_p.left);
            if (treeNode_p.right != null) stack_p.push(treeNode_p.right);

        }

        return false;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
